/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-11-05
 * Time: 20:40
 */
public class HashBuck {
    static class Node {
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] table = new Node[10];
    public int useSized = 0;
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;
    public void push(int key,int val) {
        int index = key % table.length;
        //1.先判断要放入的值是否已经存在，如果存在，则更换val值即可
        Node cur = table[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //2.如果不存在，则放入该节点，并头插到链表当中
        Node node = new Node(key,val);
        node.next = table[index];
        table[index] = node;
        useSized++;
        //3.判断负载因子是否超过0.75，如果超过了需要进行扩容减少冲突的发生
        if(doLoadFactor() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    private double doLoadFactor() {
        return useSized*1.0 / table.length;
    }

    private void resize() {
        //1.先实例化一个新的散列表，其长度为元数组的两倍
        Node[] newTable = new Node[2*table.length];
        //2.把原散列表中的节点重新遍历放入新的散列表中
        for (int i = 0; i < table.length; i++) {
            Node cur = table[i];
            while(cur != null) {
                int newIndex = cur.key % newTable.length;
                Node curN = cur.next;
                cur.next = newTable[newIndex];
                newTable[newIndex] = cur;
                cur = curN;
            }
        }
        //3.最后将新的散列表中赋给原散列表
        table = newTable;
    }
    public int getVal(int key) {
        int index = key % table.length;
        Node cur = table[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}
